package com.yxp.offer;

import com.yxp.middle.Problem1008;
import com.yxp.util.TreeNode;

/**
 * @author : yang.xp
 * @date : 2021/8/19 9:17
 * @description : 剑指 Offer 26. 树的子结构 DFS TODO
 */
public class Problem26 {

    public static void main(String[] args) {
        Problem26 problem26 = new Problem26();
        int[] numbersA = new int[]{8, 5, 1, 7, 10, 12};
        Problem1008 problem1008 = new Problem1008();
        TreeNode treeNodeA = problem1008.bstFromPreorder(numbersA);
        int[] numbersB = new int[]{8, 5, 1, 7};
        TreeNode treeNodeB = problem1008.bstFromPreorder(numbersB);
        System.out.println(problem26.isSubStructure(treeNodeA, treeNodeB));
    }


    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean dfs(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null) return false;
        return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
    }
}
